package com.y.utils;

import java.util.Arrays;

/**
 * @author Y2014188432
 * KMP 算法
 * 用于字符串中求包含的字符串
 */
public class KMP {
    public static void main(String[] args) {
        int result = kmp("asdf","f");
        System.out.println(result);
    }
    public static int kmp(String a,String b){
        String[] ta = a.split("");
        String[] tb = b.split("");
        int[] next = getNext(b);
        int i = 0;
        int j = 0;
        while (true){
            if(j == tb.length){
                return i - tb.length;
            }
            if(i == ta.length){
                return -1;
            }
            if (ta[i].equals(tb[j])){
                i ++; j ++;
            } else {
                j = next[j];
                if(j == -1){
                    i ++;
                    j ++;
                }
            }
        }
    }
    public static int[] getNext(String str){
        String[] s = str.split("");
        int[] next = new int[s.length];
        next[0] = -1;
        int i=0,k=-1;
        while (i<s.length-1){
            if(k == -1 || s[i].equals(s[k])){
                i ++;k ++;
                next[i] = k;
            }
            else{
                k = next[k];
            }
        }
        return next;
    }

}
